﻿#define _CRT_SECURE_NO_WARNINGS 1
//https://leetcode.cn/problems/reverse-linked-list/description/
//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
//输入：head = [1, 2, 3, 4, 5]
//输出：[5, 4, 3, 2, 1]
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 struct ListNode {
     int val;
     struct ListNode *next;
 };
typedef struct ListNode ListNode;


struct ListNode* reverseList(struct ListNode* head) 
{
    if (head == NULL)
    {
        return head;
    }
    ListNode* l1 = NULL;
    ListNode* l2 = head;
    ListNode* l3 = head->next;
    while (l3)
    {
        l2->next = l1;
        l1 = l2;
        l2 = l3;
        l3 = l3->next;
        l2->next = l1;

    }
    return l2;
}

//5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
//https://leetcode.cn/problems/merge-two-sorted-lists/description/


struct ListNode {
     int val;
     struct ListNode *next;
 };
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    if (list1 == NULL && list2 == NULL)
    {
        return NULL;
    }
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    ListNode* l3 = head;

    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            l3->next = list1;
            list1 = list1->next;
        }
        else
        {
            l3->next = list2;
            list2 = list2->next;
        }
        l3 = l3->next;
    }
    if (list1)
    {
        l3->next = list1;
    }
    if (list2)
    {
        l3->next = list2;
    }
    
    l3 = head;
    head = head->next;
    free(l3);
    return head;
}



//7.链表的回文结构
//https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

struct ListNode {
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};



class PalindromeList {
public:


    bool chkPalindrome(ListNode* A) {

        ListNode* lesshead = A;
 
        ListNode* gratehead = A;
      
        while (gratehead&&gratehead->next)
        {
            lesshead = lesshead->next;
            gratehead = gratehead->next->next;
        }
        ListNode* right= reverseList(lesshead);
        ListNode* left = A;
        while (right)
        {
            if (right->val != left->val)
            {
                return false;
            }
            right = right->next;
            left = left->next;
        }
        return true;
        // write code here
    }
};


//6.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
//https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking


class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        if (pHead == NULL)
        {
            return pHead;
        }
        ListNode* lesshead = (ListNode*)malloc(sizeof(ListNode));
        ListNode* lesstail= lesshead;
        ListNode* gratehead = (ListNode*)malloc(sizeof(ListNode));
        ListNode* gratetail = gratehead;
        while (pHead)
        {
            if (pHead->val < x)
            {
                lesstail->next = pHead;
                lesstail = lesstail->next;
            }
            else
            {
                gratetail->next = pHead;
                gratetail = gratetail->next;
            }
            pHead = pHead->next;
        }
        gratetail->next = NULL;

        lesstail->next = gratehead->next;
        ListNode* phead = lesshead->next;
        free(lesshead);
        free(gratehead);
        return phead;
    }
};




int mian()
{

    return 0;
}
